package com.zwj.interview.基本运算;

import java.util.Arrays;

/**
 * @Author: Zwj
 * @Date: 2022/3/1 11:20
 */
public class 求一个数之内的素数个数 {

    //我们采用筛选法，比如，2是素数，那么2的倍数的数字肯定不是素数，3是素数，那么3的倍数的数字肯定不是素数
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        //素数从2开始算起
        for (int i = 2; i < n; i++) {
            //如果i是素数，那么i的倍数的数字肯定就不是素数
            if (isPrime[i]) {
                for (int j = 2 * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        return count;
    }

    public int countPrimes2(int n) {
       boolean[]  result=new boolean[n];
       Arrays.fill(result,true);
       for(int i=2;i<n;i++){
           //最小的素数是2
           if(result[i]){
               for(int j=2*i;j<n;j+=i){
                   result[j]=false;
               }
           }
       }
       int count=0;
       for(int i=2;i<n;i++){
          if(result[i]){
              count++;
          }
       }
       return count;

    }
}